package leetcode_100;

import java.util.LinkedList;
import java.util.List;

/**
 * 2018年5月17日 上午11:28:53
 * @author 周杨
 * describe : n位元格雷码是基于n-1位元格雷码产生的。 用递归生成 其中注意使用移位运算 AC 100%
 * GrayCode_89 给定一个N 输出n位的格雷码的十进制数据
 */
public class GrayCode_89 {

	public static void main(String[] args) {
		GrayCode_89 test=new GrayCode_89();
		test.grayCode(3);

	}
	
	public List<Integer> grayCode(int n) {
		List<Integer> result = new LinkedList<>();
        if(n==0){
            result.add(0);
            return result;
        }
        if(n==1){
            result.add(0);
            result.add(1);
            return result;
        }
        int[] res=produce(n);
        for(int i=0;i<res.length;i++){
            result.add(res[i]);
        }
        return result;
    }
	
	public int[] produce(int n) {
        int[] strArr=new int[(int) Math.pow(2, n)];//产生至少2的n次方位数的格雷码
        if(n==1){
            strArr[0]=0;
            strArr[1]=1;
            return strArr;
        }
        int[] lastStrings=produce(n-1);     //当前n的格雷码 从 n-1的格雷码中产生
        for(int i=0;i<lastStrings.length;i++){//前面的格雷码是相同的
            strArr[i]=lastStrings[i];
            strArr[strArr.length-1-i]=(1<<(n-1))+lastStrings[i];//反向保存 直接二进制转10进制 后面的所有结果用1左移n-1位  直接用二进制运算
        }
        return strArr;
    }

}
